#include <iostream>
using namespace std;
// DoubleList.h双链表类定义

// 双链表节点
struct DoubleListNode {
    int data;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int val);
};

// 双链表
class DoubleList {
public:
    DoubleListNode* dummy;
public:
    DoubleList();
    ~DoubleList();
public:
    void add(int);
    void remove(int);
    DoubleListNode* find(int);
};
//函数

DoubleListNode::DoubleListNode(int val) 
    : data(val), prev(nullptr), next(nullptr) { }

DoubleList::DoubleList() : dummy(new DoubleListNode(-1)) {
    dummy->prev = dummy;//循环
    dummy->next = dummy;
}
//析构
DoubleList::~DoubleList() {
    auto ptr = dummy->next;
    while (ptr!=dummy) {
        auto temp = ptr;
        ptr = ptr->next;
        delete temp;
        
    }
    delete dummy;
    
}

//添加,头节点后插入
void DoubleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        cerr << val << " 数据已存在, 添加失败" << endl;
    }
    else {
        auto temp = new DoubleListNode(val);
        temp->next = dummy->next;
        temp->prev = dummy;
        if (dummy->next)
            dummy->next->prev = temp;
        dummy->next = temp;
    }
}
//删除
void DoubleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        cerr << val << " 数据不存在，删除失败" << endl;
    }
    else {
        if (ptr->next)
            ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        delete ptr;
    }
}
//查找
DoubleListNode* DoubleList::find(int val) {
    auto temp = dummy->next;
    while (temp!= dummy) {
        if (temp->data == val)
            return temp;
        temp = temp->next;
    }
    return nullptr;
}

// 测试


int main(void) {
	DoubleList list;

	list.add(0);
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(4);	// 添加已存在元素
	list.remove(0); // 末尾元素
	list.remove(2); // 中间元素
	list.remove(4); // 开头元素
	list.remove(4); // 删除不存在元素
	for (auto temp = list.dummy->next; temp!=list.dummy; temp = temp->next)
		cout << temp->data << " ";
	cout << endl;
	
	return 0;
}
